package com.ljy.my_study.leetcode.验证二叉搜索树;

import com.ljy.my_study.util.TreeNodeUtil;
import com.ljy.my_study.util.TreeNodeUtil.*;

/**
 * @author lijunying
 * @date 2021/11/16 13:56
 */
public class TestMain {

//    给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
//
//    有效 二叉搜索树定义如下：
//
//    节点的左子树只包含 小于 当前节点的数。
//    节点的右子树只包含 大于 当前节点的数。
//    所有左子树和右子树自身必须也是二叉搜索树。
//             
//
//    示例 1：
//
//
//    输入：root = [2,1,3]
//    输出：true
//    示例 2：
//
//
//    输入：root = [5,1,4,null,null,3,6]
//    输出：false
//    解释：根节点的值是 5 ，但是右子节点的值是 4 。
//             
//
//    提示：
//
//    树中节点数目范围在[1, 104] 内
//-2^31 <= Node.val <= 2^31 - 1
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/validate-binary-search-tree
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//    dfs
    public static void main(String[] args) {
        TreeNode root=TreeNodeUtil.deserialize("2147483647");
        System.out.println(new TestMain().isValidBST(root));
    }

    public boolean isValidBST(TreeNode root) {
        return dfs(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    private boolean dfs(TreeNode node,long left,long right){
        if(node==null){
            return true;
        }
        if(node.val<=left||node.val>=right){
            return false;
        }
        return dfs(node.left,left,node.val)&&dfs(node.right,node.val,right);
    }
}
